home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3181 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.3 KB

  1. Path: news.umbc.edu!not-for-mail
  2. From: schlein@umbc.edu (Jonas J. Schlein)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Loop Invariant
  5. Date: 26 Jan 1996 14:01:36 -0500
  6. Organization: University of Maryland Baltimore County
  7. Message-ID: <4eb8eg$7lg@umbc9.umbc.edu>
  8. References: <4e42pg$2oq@sanjuan.islandnet.com>
  9. NNTP-Posting-Host: umbc9.umbc.edu
  10. NNTP-Posting-User: schlein
  11.  
  12. Jason Klinke <jklinke@uvaix.uvic.ca> wrote:
  13. |> I'm having difficulty coming up with a loop invariant that I can prove, for
  14. |> the following code which computes the sum of the integers in the array 
  15. |> A[0..n-1] :
  16. |> 
  17. |> -----------
  18. |> sum = 0;
  19. |> for (i = 0; i < n; i++)
  20. |>     sum = sum + A[i];
  21. |> -----------
  22. |> 
  23. |> Any help with this invariant and its proof is appreciated.
  24.  
  25. Do it by induction...Verify that it works for the sum of the integers in
  26. am empty array (or an array with only 1 element). Then assume it works
  27. for any array with n-1 elements and from that prove that this implies
  28. it also works for an array with n elements.
  29.  
  30. Basically this idea is called mathematical induction. There is a weak and
  31. strong form. I can't believe your teacher did not tell you about this
  32. since that is obviously what is probably intended.
  33. -- 
  34. "If it wasn't for C, we would be using BASI, PASAL, and OBOL."
  35.  
  36. Jonas J. Schlein  (schlein@gl.umbc.edu)
  37.